package NO6_Tree;

import java.util.Arrays;

/**
 * 2025-09-16
 * 力扣 - 106. 从中序与后序遍历序列构造二叉树
 * <p>
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
 * postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 */
public class BuildTree2Main {
    public static void main(String[] args) {
        int[] inorder = {9, 3, 15, 20, 7};
        int[] postorder = {9, 15, 7, 20, 3};
        TreeNode.printTree(buildTree(inorder, postorder));
    }

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }

        // 后序遍历的最后一个元素就是根节点
        int rootVal = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int rootIndex = -1;
        for (int i = 0; i < inorder.length; i++){
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        // 构建左子树
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, rootIndex);
        int[] leftPostorder = Arrays.copyOfRange(postorder, 0, rootIndex);
        root.left = buildTree(leftInorder, leftPostorder);

        // 构建右子树
        int[] rightInorder = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);
        int[] rightPostorder = Arrays.copyOfRange(postorder, rootIndex, postorder.length - 1);
        root.right = buildTree(rightInorder, rightPostorder);

        return root;
    }
}
